package com.fengye.algorithms.leecode;

import com.fengye.algorithms.leecode.common.Node;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author fengye
 * @Date 2023/4/26 9:22
 **/
public class PopulatingNextRightPointersInEachNodeII117 {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);
        Node node11 = new Node(11);
        Node node12 = new Node(12);
        Node node13 = new Node(13);
        Node node14 = new Node(14);
        Node node15 = new Node(15);
        node1.left = node2;
        node1.right = node3;
        //node2.left = node4;
        //node2.right = node5;
        node3.left = node6;
        node3.right = node7;
//        node4.left = node8;
//        node4.right = node9;
//        node5.left = node10;
//        node5.right = node11;
//        node6.left = node12;
//        node6.right = node13;
//        node7.left = node14;
//        node7.right = node15;


        new PopulatingNextRightPointersInEachNodeII117().connect(node1);
    }

    /**
     * 通过根节点来处理
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if(root == null) {
            return root;
        }

        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int count = queue.size();
            Node pre = null;
            for(int i=0;i<count;i++) {
                Node node = queue.poll();
                // 如果pre != null, 说明不是第一个
                if(pre != null) {
                    pre.next = node;
                }
                pre = node;

                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
        }

        return root;
    }

    public Node connect2(Node root) {
        if (root == null)
            return root;
        //cur我们可以把它看做是每一层的链表
        Node cur = root;
        while (cur != null) {
            //遍历当前层的时候，为了方便操作在下一
            //层前面添加一个哑结点（注意这里是访问
            //当前层的节点，然后把下一层的节点串起来）
            Node dummy = new Node(0);
            //pre表示访下一层节点的前一个节点
            Node pre = dummy;
            //然后开始遍历当前层的链表
            while (cur != null) {
                if (cur.left != null) {
                    //如果当前节点的左子节点不为空，就让pre节点
                    //的next指向他，也就是把它串起来
                    pre.next = cur.left;
                    //然后再更新pre
                    pre = pre.next;
                }
                //同理参照左子树
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = pre.next;
                }
                //继续访问这一行的下一个节点
                cur = cur.next;
            }
            //把下一层串联成一个链表之后，让他赋值给cur，
            //后续继续循环，直到cur为空为止
            cur = dummy.next;
        }
        return root;
    }

}
